/*-------------------------------------------------------------------------
 *
 * rbtree.c
 *	  PostgreSQL 通用红黑树包的实现
 *	  采用自 http://algolist.manual.ru/ds/rbtree.php
 *
 * 此代码来自托马斯·尼曼（Thomas Niemann）的《排序和搜索算法：一本食谱》。
 *
 * 参见 http://www.cs.auckland.ac.nz/software/AlgAnim/niemann/s_man.htm 的许可条款：
 * “源代码，当它是软件项目的一部分时，可以自由使用，无需提及作者。”
 *
 * 红黑树是一种平衡二叉树，其中 (1) 红色节点的任何子节点始终是黑色的，(2) 从根到叶的每一条路径遍历
 * 相同数量的黑色节点。根据这些属性，根到叶的最长路径仅约是最短路径的两倍，
 * 所以查找保证在 O(lg n) 时间内运行。
 *
 * Copyright (c) 2009-2022, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *	  src/backend/lib/rbtree.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "lib/rbtree.h"


/*
 * 节点的颜色（RBTNode.color的值）
 */
#define RBTBLACK	(0)
#define RBTRED		(1)

/*
 * RBTree控制结构
 */
struct RBTree
{
	RBTNode    *root;			/* 根节点，或在树为空时为RBTNIL */

	/* 在rbt_create之后，剩余字段是常量 */

	Size		node_size;		/* 树节点的实际大小 */
	/* 调用者提供的操作函数 */
	rbt_comparator comparator;
	rbt_combiner combiner;
	rbt_allocfunc allocfunc;
	rbt_freefunc freefunc;
	/* 传递给所有操作函数的参数 */
	void	   *arg;
};

/*
 * 所有叶子节点都是哨兵，使用自定义的NIL名称以防止
 * 与全局常量NIL发生冲突，实际上是NULL
 */
#define RBTNIL (&sentinel)

static RBTNode sentinel =
{
	RBTBLACK, RBTNIL, RBTNIL, NULL
};


/*
 * rbt_create：创建一个空的RBTree
 *
 * 参数为：
 *	node_size：树节点的实际大小（> sizeof(RBTNode））
 *	操作函数：
 *	comparator：比较两个RBTNodes的大小，返回小于/等于/大于
 *	combiner：将现有树条目与新条目合并
 *	allocfunc：分配一个新的RBTNode
 *	freefunc：释放一个旧的RBTNode
 *	arg：将传递给操作函数的透传指针
 *
 * 请注意，combiner的右侧参数将是一个“提议”的树节点，
 * 即rbt_insert的输入，其中RBTNode字段本身无效。
 * 同样，传递给比较函数的任一输入可能是一个“提议”的节点。
 * 这应该不成问题，因为这些函数不应该查看RBTNode字段，
 * 只应查看RBTNode嵌入的结构的额外字段。
 *
 * freefunc应该只是pfree或等效；它不应尝试
 * 释放任何附属数据，因为传递给它的节点可能不包含
 * 有效数据！如果调用者不需要零售空间回收
 * freefunc可以为NULL。
 *
 * RBTree节点在调用者的内存上下文中分配。请注意，
 * 树的所有内容实际上都是由调用者分配的，而不是在此处分配。
 *
 * 由于树的内容由调用者管理，目前没有
 * 明确的“销毁”操作；通常，树会通过
 * 重置或删除它存储的内存上下文来释放。如果
 * 你觉得有必要，可以pfree RBTree节点。
 */
RBTree *
rbt_create(Size fc_node_size,
		   rbt_comparator fc_comparator,
		   rbt_combiner fc_combiner,
		   rbt_allocfunc fc_allocfunc,
		   rbt_freefunc fc_freefunc,
		   void *fc_arg)
{
	RBTree	   *fc_tree = (RBTree *) palloc(sizeof(RBTree));

	Assert(fc_node_size > sizeof(RBTNode));

	fc_tree->root = RBTNIL;
	fc_tree->node_size = fc_node_size;
	fc_tree->comparator = fc_comparator;
	fc_tree->combiner = fc_combiner;
	fc_tree->allocfunc = fc_allocfunc;
	fc_tree->freefunc = fc_freefunc;

	fc_tree->arg = fc_arg;

	return fc_tree;
}

/* 从一个RBTNode复制额外的数据字段到另一个RBTNode */
static inline void fc_rbt_copy_data(RBTree *fc_rbt, RBTNode *fc_dest, const RBTNode *fc_src)
{
	memcpy(fc_dest + 1, fc_src + 1, fc_rbt->node_size - sizeof(RBTNode));
}

/**********************************************************************
 *						  搜索									  *
 **********************************************************************/

/*
 * rbt_find：在RBTree中搜索一个值
 *
 * data表示要尝试查找的值。其RBTNode字段不必
 * 是有效的，我们关注的是更大结构中的额外数据。
 *
 * 返回匹配的树条目，如果没有找到匹配则返回NULL。
 */
RBTNode * rbt_find(RBTree *fc_rbt, const RBTNode *fc_data)
{
	RBTNode    *fc_node = fc_rbt->root;

	while (fc_node != RBTNIL)
	{
		int			fc_cmp = fc_rbt->comparator(fc_data, fc_node, fc_rbt->arg);

		if (fc_cmp == 0)
			return fc_node;
		else if (fc_cmp < 0)
			fc_node = fc_node->left;
		else
			fc_node = fc_node->right;
	}

	return NULL;
}

/*
 * rbt_leftmost：获取最左侧（最小值）树节点。
 * 如果树为空，则返回NULL。
 *
 * 注意：在原始实现中这包括解除链接步骤，但
 * 这有点尴尬。如果这是你想要的，只需在结果上调用rbt_delete。
 */
RBTNode * rbt_leftmost(RBTree *fc_rbt)
{
	RBTNode    *fc_node = fc_rbt->root;
	RBTNode    *fc_leftmost = fc_rbt->root;

	while (fc_node != RBTNIL)
	{
		fc_leftmost = fc_node;
		fc_node = fc_node->left;
	}

	if (fc_leftmost != RBTNIL)
		return fc_leftmost;

	return NULL;
}

/**********************************************************************
 *							  插入								  *
 **********************************************************************/

/*
 * 将节点 x 向左旋转。
 *
 * x 的右子节点在树中取代它的位置，x 成为该节点的左子节点。
 */
static void fc_rbt_rotate_left(RBTree *fc_rbt, RBTNode *fc_x)
{
	RBTNode    *fc_y = fc_x->right;

	/* 建立 x->right 链接 */
	fc_x->right = fc_y->left;
	if (fc_y->left != RBTNIL)
		fc_y->left->parent = fc_x;

	/* 建立 y->parent 链接 */
	if (fc_y != RBTNIL)
		fc_y->parent = fc_x->parent;
	if (fc_x->parent)
	{
		if (fc_x == fc_x->parent->left)
			fc_x->parent->left = fc_y;
		else
			fc_x->parent->right = fc_y;
	}
	else
	{
		fc_rbt->root = fc_y;
	}

	/* 连接 x 和 y */
	fc_y->left = fc_x;
	if (fc_x != RBTNIL)
		fc_x->parent = fc_y;
}

/*
 * 将节点 x 向右旋转。
 *
 * x 的左子节点的右子节点在树中取代它的位置，x 成为该节点的右子节点。
 */
static void fc_rbt_rotate_right(RBTree *fc_rbt, RBTNode *fc_x)
{
	RBTNode    *fc_y = fc_x->left;

	/* 建立 x->left 链接 */
	fc_x->left = fc_y->right;
	if (fc_y->right != RBTNIL)
		fc_y->right->parent = fc_x;

	/* 建立 y->parent 链接 */
	if (fc_y != RBTNIL)
		fc_y->parent = fc_x->parent;
	if (fc_x->parent)
	{
		if (fc_x == fc_x->parent->right)
			fc_x->parent->right = fc_y;
		else
			fc_x->parent->left = fc_y;
	}
	else
	{
		fc_rbt->root = fc_y;
	}

	/* 连接 x 和 y */
	fc_y->right = fc_x;
	if (fc_x != RBTNIL)
		fc_x->parent = fc_y;
}

/*
 * 在插入节点 x 后维护红黑树的平衡。
 *
 * 新插入的节点总是最初标记为红色。这可能导致一个红色节点有一个红色子节点，这是被禁止的。我们总是可以通过一系列的颜色改变和/或“旋转”来修复这个问题，这将问题逐渐向树的更高处移动。如果两个红色节点中的一个是根节点，我们总是可以通过将根节点从红色改为黑色来修复这个问题。
 *
 * （这在树的下方不起作用，因为我们还必须保持每个叶子节点的黑色高度相等的特性。）
 */
static void fc_rbt_insert_fixup(RBTree *fc_rbt, RBTNode *fc_x)
{
	/*
	 * x 总是一个红色节点。最初，它是新插入的节点。这个循环的每个迭代将它向树的更高处移动。
	 */
	while (fc_x != fc_rbt->root && fc_x->parent->color == RBTRED)
	{
		/*
		 * x 和 x->parent 都是红色的。修复取决于 x->parent 是左子节点还是右子节点。在任何情况下，我们将 y 定义为 x 的“叔叔”，即 x 的祖父母的另一个孩子。
		 *
		 * 如果叔叔是红色的，我们将祖父母的颜色改为红色，而其两个孩子改为黑色。然后我们再次循环，检查祖父母是否仍然存在问题。
		 *
		 * 如果叔叔是黑色的，我们将进行一次或两次“旋转”来平衡树。x 或 x->parent 将取代祖父母在树中的位置并重新上色为黑色，原祖父母将被重新上色为红色并成为该节点的子节点。这总是会让我们保持一个有效的红黑树，因此循环将结束。
		 */
		if (fc_x->parent == fc_x->parent->parent->left)
		{
			RBTNode    *fc_y = fc_x->parent->parent->right;

			if (fc_y->color == RBTRED)
			{
				/* 叔叔是 RBTRED */
				fc_x->parent->color = RBTBLACK;
				fc_y->color = RBTBLACK;
				fc_x->parent->parent->color = RBTRED;

				fc_x = fc_x->parent->parent;
			}
			else
			{
				/* 叔叔是 RBTBLACK */
				if (fc_x == fc_x->parent->right)
				{
					/* 使 x 成为左子节点 */
					fc_x = fc_x->parent;
					fc_rbt_rotate_left(fc_rbt, fc_x);
				}

				/* 重新上色并旋转 */
				fc_x->parent->color = RBTBLACK;
				fc_x->parent->parent->color = RBTRED;

				fc_rbt_rotate_right(fc_rbt, fc_x->parent->parent);
			}
		}
		else
		{
			/* 上述代码的镜像 */
			RBTNode    *fc_y = fc_x->parent->parent->left;

			if (fc_y->color == RBTRED)
			{
				/* 叔叔是 RBTRED */
				fc_x->parent->color = RBTBLACK;
				fc_y->color = RBTBLACK;
				fc_x->parent->parent->color = RBTRED;

				fc_x = fc_x->parent->parent;
			}
			else
			{
				/* 叔叔是 RBTBLACK */
				if (fc_x == fc_x->parent->left)
				{
					fc_x = fc_x->parent;
					fc_rbt_rotate_right(fc_rbt, fc_x);
				}
				fc_x->parent->color = RBTBLACK;
				fc_x->parent->parent->color = RBTRED;

				fc_rbt_rotate_left(fc_rbt, fc_x->parent->parent);
			}
		}
	}

	/*
	 * 根节点可能已经是黑色的；如果不是，树中每个节点的黑色高度增加一。
	 */
	fc_rbt->root->color = RBTBLACK;
}

/*
 * rbt_insert: 将新值插入树中。
 *
 * data 代表要插入的值。它的 RBTNode 字段不需要有效，较大结构中的额外数据才是重要的。
 *
 * 如果 "data" 代表的值在树中不存在，则我们将 "data" 复制到新的树条目中并返回该节点，将 *isNew 设置为 true。
 *
 * 如果 "data" 代表的值已经存在，则调用合并函数将数据合并到现有节点中，并返回现有节点，将 *isNew 设置为 false。
 *
 * 在两种情况下，"data" 都未被修改；它通常只是调用者中的一个局部变量。
 */
RBTNode * rbt_insert(RBTree *fc_rbt, const RBTNode *fc_data, bool *fc_isNew)
{
	RBTNode    *fc_current,
			   *fc_parent,
			   *fc_x;
	int			fc_cmp;

	/* 查找节点属于哪里 */
	fc_current = fc_rbt->root;
	fc_parent = NULL;
	fc_cmp = 0;					/* 只是为了防止编译器警告 */

	while (fc_current != RBTNIL)
	{
		fc_cmp = fc_rbt->comparator(fc_data, fc_current, fc_rbt->arg);
		if (fc_cmp == 0)
		{
			/*
			 * 找到具有给定键的节点。应用合并器。
			 */
			fc_rbt->combiner(fc_current, fc_data, fc_rbt->arg);
			*fc_isNew = false;
			return fc_current;
		}
		fc_parent = fc_current;
		fc_current = (fc_cmp < 0) ? fc_current->left : fc_current->right;
	}

	/*
	 * 值不存在，因此创建一个包含数据的新节点。
	 */
	*fc_isNew = true;

	fc_x = fc_rbt->allocfunc(fc_rbt->arg);

	fc_x->color = RBTRED;

	fc_x->left = RBTNIL;
	fc_x->right = RBTNIL;
	fc_x->parent = fc_parent;
	fc_rbt_copy_data(fc_rbt, fc_x, fc_data);

	/* 将节点插入树中 */
	if (fc_parent)
	{
		if (fc_cmp < 0)
			fc_parent->left = fc_x;
		else
			fc_parent->right = fc_x;
	}
	else
	{
		fc_rbt->root = fc_x;
	}

	fc_rbt_insert_fixup(fc_rbt, fc_x);

	return fc_x;
}

/**********************************************************************
 *							删除								  *
 **********************************************************************/

/*
 * 在删除黑色节点后维护红黑树的平衡。
 */
static void fc_rbt_delete_fixup(RBTree *fc_rbt, RBTNode *fc_x)
{
	/*
	 * x 始终是一个黑色节点。最初，它是被删除节点的原子。每次循环迭代将其移到树中的更高位置。
	 */
	while (fc_x != fc_rbt->root && fc_x->color == RBTBLACK)
	{
		/*
		 * 左右情况是对称的。任何作为 x 子节点的节点的黑色高度比树中其余节点少一。我们旋转和重新着色节点以将问题移到树上：在某个阶段，我们将修复问题，或者到达根节点（在根节点处黑色高度是允许降低的）。
		 */
		if (fc_x == fc_x->parent->left)
		{
			RBTNode    *fc_w = fc_x->parent->right;

			if (fc_w->color == RBTRED)
			{
				fc_w->color = RBTBLACK;
				fc_x->parent->color = RBTRED;

				fc_rbt_rotate_left(fc_rbt, fc_x->parent);
				fc_w = fc_x->parent->right;
			}

			if (fc_w->left->color == RBTBLACK && fc_w->right->color == RBTBLACK)
			{
				fc_w->color = RBTRED;

				fc_x = fc_x->parent;
			}
			else
			{
				if (fc_w->right->color == RBTBLACK)
				{
					fc_w->left->color = RBTBLACK;
					fc_w->color = RBTRED;

					fc_rbt_rotate_right(fc_rbt, fc_w);
					fc_w = fc_x->parent->right;
				}
				fc_w->color = fc_x->parent->color;
				fc_x->parent->color = RBTBLACK;
				fc_w->right->color = RBTBLACK;

				fc_rbt_rotate_left(fc_rbt, fc_x->parent);
				fc_x = fc_rbt->root;	/* 安排循环终止。 */
			}
		}
		else
		{
			RBTNode    *fc_w = fc_x->parent->left;

			if (fc_w->color == RBTRED)
			{
				fc_w->color = RBTBLACK;
				fc_x->parent->color = RBTRED;

				fc_rbt_rotate_right(fc_rbt, fc_x->parent);
				fc_w = fc_x->parent->left;
			}

			if (fc_w->right->color == RBTBLACK && fc_w->left->color == RBTBLACK)
			{
				fc_w->color = RBTRED;

				fc_x = fc_x->parent;
			}
			else
			{
				if (fc_w->left->color == RBTBLACK)
				{
					fc_w->right->color = RBTBLACK;
					fc_w->color = RBTRED;

					fc_rbt_rotate_left(fc_rbt, fc_w);
					fc_w = fc_x->parent->left;
				}
				fc_w->color = fc_x->parent->color;
				fc_x->parent->color = RBTBLACK;
				fc_w->left->color = RBTBLACK;

				fc_rbt_rotate_right(fc_rbt, fc_x->parent);
				fc_x = fc_rbt->root;	/* 安排循环终止。 */
			}
		}
	}
	fc_x->color = RBTBLACK;
}

/*
 * 从树中删除节点 z。
 */
static void fc_rbt_delete_node(RBTree *fc_rbt, RBTNode *fc_z)
{
	RBTNode    *fc_x,
			   *fc_y;

	/* 这只是偏执：我们应该只在有效节点上被调用 */
	if (!fc_z || fc_z == RBTNIL)
		return;

	/*
	 * y 是将实际从树中删除的节点。如果 z 具有少于两个子节点，则 y 为 z，否则 y 为 z 的树后继。
	 */
	if (fc_z->left == RBTNIL || fc_z->right == RBTNIL)
	{
		/* y 有一个 RBTNIL 节点作为子节点 */
		fc_y = fc_z;
	}
	else
	{
		/* 查找树后继 */
		fc_y = fc_z->right;
		while (fc_y->left != RBTNIL)
			fc_y = fc_y->left;
	}

	/* x 是 y 唯一的子节点 */
	if (fc_y->left != RBTNIL)
		fc_x = fc_y->left;
	else
		fc_x = fc_y->right;

	/* 从树中移除 y。 */
	fc_x->parent = fc_y->parent;
	if (fc_y->parent)
	{
		if (fc_y == fc_y->parent->left)
			fc_y->parent->left = fc_x;
		else
			fc_y->parent->right = fc_x;
	}
	else
	{
		fc_rbt->root = fc_x;
	}

	/*
	 * 如果我们移除了 z 的树后继而不是 z 本身，则将被移除节点的数据移到我们应该移除的节点上。
	 */
	if (fc_y != fc_z)
		fc_rbt_copy_data(fc_rbt, fc_z, fc_y);

	/*
	 * 移除黑色节点可能使从根到叶的某些路径的黑色节点数量少于其他路径，或者可能使两个红色节点相邻。
	 */
	if (fc_y->color == RBTBLACK)
		fc_rbt_delete_fixup(fc_rbt, fc_x);

	/* 现在我们可以回收 y 节点了 */
	if (fc_rbt->freefunc)
		fc_rbt->freefunc(fc_y, fc_rbt->arg);
}

/*
 * rbt_delete: 移除给定的树条目
 *
 * "node" 必须之前通过 rbt_find 或 rbt_leftmost 找到。在调用 rbt_delete 之前，调用者有责任释放附加在节点上的任何附属数据。 (不要试图将该责任推给 freefunc，因为其他物理节点可能是实际被释放的节点！)
 */
void rbt_delete(RBTree *fc_rbt, RBTNode *fc_node)
{
	fc_rbt_delete_node(fc_rbt, fc_node);
}

/**********************************************************************
 *						  遍历									  *
 **********************************************************************/

static RBTNode * fc_rbt_left_right_iterator(RBTreeIterator *fc_iter)
{
	if (fc_iter->last_visited == NULL)
	{
		fc_iter->last_visited = fc_iter->rbt->root;
		while (fc_iter->last_visited->left != RBTNIL)
			fc_iter->last_visited = fc_iter->last_visited->left;

		return fc_iter->last_visited;
	}

	if (fc_iter->last_visited->right != RBTNIL)
	{
		fc_iter->last_visited = fc_iter->last_visited->right;
		while (fc_iter->last_visited->left != RBTNIL)
			fc_iter->last_visited = fc_iter->last_visited->left;

		return fc_iter->last_visited;
	}

	for (;;)
	{
		RBTNode    *fc_came_from = fc_iter->last_visited;

		fc_iter->last_visited = fc_iter->last_visited->parent;
		if (fc_iter->last_visited == NULL)
		{
			fc_iter->is_over = true;
			break;
		}

		if (fc_iter->last_visited->left == fc_came_from)
			break;				/* 来自左子树，返回当前节点 */

		/* 否则 - 来自右子树，继续向上移动 */
	}

	return fc_iter->last_visited;
}

static RBTNode * fc_rbt_right_left_iterator(RBTreeIterator *fc_iter)
{
	if (fc_iter->last_visited == NULL)
	{
		fc_iter->last_visited = fc_iter->rbt->root;
		while (fc_iter->last_visited->right != RBTNIL)
			fc_iter->last_visited = fc_iter->last_visited->right;

		return fc_iter->last_visited;
	}

	if (fc_iter->last_visited->left != RBTNIL)
	{
		fc_iter->last_visited = fc_iter->last_visited->left;
		while (fc_iter->last_visited->right != RBTNIL)
			fc_iter->last_visited = fc_iter->last_visited->right;

		return fc_iter->last_visited;
	}

	for (;;)
	{
		RBTNode    *fc_came_from = fc_iter->last_visited;

		fc_iter->last_visited = fc_iter->last_visited->parent;
		if (fc_iter->last_visited == NULL)
		{
			fc_iter->is_over = true;
			break;
		}

		if (fc_iter->last_visited->right == fc_came_from)
			break;				/* 来自右子树，返回当前节点 */

		/* 否则 - 来自左子树，继续向上移动 */
	}

	return fc_iter->last_visited;
}

/*
 * rbt_begin_iterate: 准备以多种顺序遍历树
 *
 * 调用 rbt_begin_iterate 后，重复调用 rbt_iterate，直到它
 * 返回 NULL 或遍历不再感兴趣。
 *
 * 如果在遍历过程中更改了树，后续调用 rbt_iterate 的结果是未指定的。允许在同一
 * 树上有多个同时进行的迭代器。
 *
 * 迭代器状态存储在 'iter' 结构中。调用者应将其视为不透明的结构。
 */
void rbt_begin_iterate(RBTree *fc_rbt, RBTOrderControl fc_ctrl, RBTreeIterator *fc_iter)
{
	/* 所有遍历顺序的常见初始化 */
	fc_iter->rbt = fc_rbt;
	fc_iter->last_visited = NULL;
	fc_iter->is_over = (fc_rbt->root == RBTNIL);

	switch (fc_ctrl)
	{
		case LeftRightWalk:		/* 先访问左子树，然后是自己，然后是右子树 */
			fc_iter->iterate = fc_rbt_left_right_iterator;
			break;
		case RightLeftWalk:		/* 先访问右子树，然后是自己，然后是左子树 */
			fc_iter->iterate = fc_rbt_right_left_iterator;
			break;
		default:
			elog(ERROR, "unrecognized rbtree iteration order: %d", fc_ctrl);
	}
}

/*
 * rbt_iterate: 返回遍历顺序中的下一个节点，如果没有更多则返回 NULL
 */
RBTNode * rbt_iterate(RBTreeIterator *fc_iter)
{
	if (fc_iter->is_over)
		return NULL;

	return fc_iter->iterate(fc_iter);
}
